package com.code.leetcode.offer;

import com.code.leetcode.offer.tutils.Node;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/8/1 21:58
 */
public class The36 {

    Deque<Node> deque = new LinkedList<>();

    public Node treeToDoublyList(Node root) {
        dfs(root);
        if (deque.isEmpty()) return null;
        Node head = deque.poll();
        Node rtn = head;
        Node node;
        while (!deque.isEmpty()) {
            node = deque.poll();
            node.left = head;
            head.right = node;
            head = node;
        }
        rtn.left = head;
        head.right = rtn;
        return rtn;
    }

    public void dfs(Node root) {
        if (root == null) return;
        dfs(root.left);
        deque.addLast(root);
        dfs(root.right);
    }
}
